A technique of performing a path search is known in which when a path from a departure point to a destination point is searched for by an on-vehicle navigation device according to the map information, map data is divided into rectangular areas along the lines of latitude and longitude and the map data of a specific area is read. In this technique, the area through which the straight line that connects a departure point with a destination point passes is firstly specified and the map data is read, and then some area is specified from a square area that has the straight line as the diagonal line and the map data is read. Accordingly, the map data required for the navigation is efficiently retrieved.
Moreover, a technique is also known in which when a path search is performed according to the map information, roads are classified into one of two or more levels depending on the type of road and one level is selected therefrom. In this technique, a tentative departure point and a tentative destination point on the road network of the selected level are calculated, and a path from the departure point to the destination point is calculated by utilizing in combination the shortest path on the subject road network, a connection path from the departure point to the tentative departure point, and a connection path from the tentative destination point to the destination point. The path-searching period may be shortened by limiting the search target to roads at one level.
As path searching algorithms based on a cost, various kinds of algorithms such as Dijkstra's algorithm and the A* algorithm are known.
In Dijkstra's algorithm, a path with the lowest cost may be efficiently calculated by setting a cost to each edge between nodes and calculating a combination of edges at which the cost is relatively small as a candidate path from a beginning node to an end node.
The A* algorithm is a modified Dijkstra's algorithm for further improved efficiency. In the A* algorithm, a path with the lowest cost is searched for by adding to the cost of Dijkstra's algorithm an estimated value (heuristic value) of the cost of reaching an end node. Accordingly, the area to be searched may be narrowed down to improve the efficiency of processing.    Patent Document 1: Japanese Laid-open Patent Publication No. 2006-162273    Patent Document 2: Japanese Laid-open Patent Publication No. 06-052237    Non-patent Document 1: E. W. Dijkstra, “A Note on Two Problems In Connexion with Graphs”, Numerische Mathematik 1, pp. 269-271, 1959.    Non-patent Document 2: P. E. Hart, N. J. Nilsson, B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions of Systems Science and Cybernetics, Vol. SSC-4, No. 2, pp. 100-107, 1968.